1. Field of the Invention
This invention relates generally to the field of digital printing and specifically to systems and methods for compressing bitonal black and white and color images.
2. Description of the Related Art
Conventional digital printing systems operate on bitonal images. Bitonal images are images, whether black and white or color, that are represented on a page by a plurality of dots or "pixels" wherein each dot (or "pixel") generally has one of two states (e.g. is either on or off). In these systems an "on" dot (or pixel) causes colorant to be applied and an "off" dot (or pixel) causes no colorant to be applied at the corresponding location on the page. In black and white systems, an "on" dot (or pixel) generally causes black colorant to be applied. Color systems similarly turn on and off dots (or pixels) to generate an image. Color systems, however, superimpose "dots" (or pixels) of different colorants to generate a desired color. For example, some color systems generate color by superimposing cyan, magenta and yellow (CMY) colorants or by superimposing cyan, magenta, yellow and black (CMYK) colorants. In such color systems, the bitonal color image is represented by a plurality of bitonal sets of data (color planes), each corresponding to a colorant.
Generally, an image is initially generated as a contone image and then later converted to a bitonal image for printing. For example, a person using an image editing program or using an image scanning device will generate a contone image and in the course of printing, the image is generally converted to a bitonal representation. A contone image is represented by a plurality of dots or pixels wherein each dot or pixel has a range of tonal values, as opposed to binary values as in bitonal images. Some examples of possible tonal ranges for each pixel in a contone images are 16 tonal values (4 bit), 32 tonal values (5 bit), 64 tonal values (6 bit), 128 tonal values (7 bit) and 256 tonal values (8 bit).
Conventional digital printing systems receive data corresponding to text and graphics in a variety of formats. These systems process such data to create bitonal images suitable for printing by the particular print engine in the system.
A conventional technique for processing images is to incorporate a microprocessor into a printing device, and to program the microprocessor to interpret commands from an attached computer in accordance with the protocols of a page description language. Such subsystems are commonly known as "interpreters", and translate the printing commands from the attached computer into commands and bitonal image data more easily processed by the printing device.
In practice, it is common for interpreters to decompose high-level commands corresponding to complex images into low-level commands representing, for instance, a collection of simple components known as "graphic primitives".
Two system architectures are commonly used in the industry for further processing of the low-level commands produced by page description language interpreters. The first, known as a "frame buffer", represents every bitonal pixel on a printed page as a separate bit or, in the case of color, as a set of bits in random access memory (RAM). Under this system, any page that can be described as a map of bitonal pixels can be printed. Frame buffer systems typically must process the information to be displayed on a frame-by-frame basis in which each frame must be rasterized and the data therein sent serially to the print engine. Furthermore, a substantial amount of frame buffer RAM is required to store information for the page, even when the image to be printed is extremely simple.
The second common architecture, known as "banding", stores all of the graphic primitives to be printed on the page, such as characters, graphics, images, and the like, in one or more "display lists" stored in the RAM of the printing system. One example of a system using such an architecture is disclosed in U.S. Pat. No. 5,500,928 issued to Cook et. al, the contents of which are incorporated herein by reference. A display list is typically a temporally-ordered list of graphic primitives for one area of the page, typically a horizontal band. Each display list is rasterized in turn into one of a small number of band bit maps (or "pixel maps"), or buffers, the contents of which are sent in turn to the print engine. The band buffers are reused during the processing of all the display lists of the page. Typically, most of the rasterization into band pixel maps occurs after the print engine has started to print the page. In the typical laser printer, the engine cannot be stopped in the middle of a page, so this rasterization must be fast enough to keep up with the print engine. In banding systems, relatively little RAM is required to print simple pages, and processing of one page while another page is printing is possible. However, for very complex images the size of the lists can exceed the RAM resulting in an error. Thus, sufficient RAM for handling such complex images must be provided or an error will result. Additionally, the bands must be rasterized within the time requirements of the printer engine or an error will result.
Some prior art systems perform lossless compression on selected bands of bitonal image data when the memory requirements for the bitonal image approach or exceed the available memory. In some instances, however, the lossless compression does not provide sufficient compression to meet the memory constraints of a particular system and in these instances, a page prints with an error such as being printed across multiple sheets.